package leetcode_1_200;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_120_timeout {
    public static void main(String[] args) {
        List<List<Integer>> tes = new ArrayList<>();
        ArrayList<Integer> l1 = new ArrayList<>();
        l1.add(2);
        tes.add(l1);
        ArrayList<Integer> l2 = new ArrayList<>();
        l2.add(3);
        l2.add(4);
        tes.add(l2);
        System.out.println(minimumTotal(tes));
    }
    private static int minimumTotal(List<List<Integer>> triangle) {
        int[] min = new int[1];
        min[0] = Integer.MAX_VALUE;
        f(triangle, 0, 0,0, min);
        return min[0];
    }
    private static void f(List<List<Integer>> triangle, int sum, int depth,int i, int[] min){
        if (depth >= triangle.size() || i >= triangle.get(depth).size())
            return;
        List<Integer> list = triangle.get(depth);
        if (depth == triangle.size() - 1){
            min[0] = Math.min(min[0], sum + list.get(i));
        }
        f(triangle,  sum + list.get(i), depth + 1, i, min);
        f(triangle,  sum + list.get(i), depth + 1, i + 1, min);
    }
}
